import java.util.*;

/**
 * Created by safe on 2017-03-28.
 * <p>
 * 动态规划思路
 * 1.描述一个最优解的结构
 * 2.递归定义一个最优解
 * 3.按自底向上的方式计算一个最优解的值
 */
public class Graph {
    private Color[] color;
    //节点个数
    private int nodeCount;
    //链路个数
    private int edgeCount;
    //消费节点个数
    private int consumerConut;
    // 邻接表表头数组
    Node[] firstArray;
    // 消费节点表头数组
    Map<Integer, Integer>[] consumerArray;
    //d[v] s-->的距离
    private int[] d;
    //pai[v]=u v的前驱点是u （v，u）
    private int[] pai;
    //finish time
    private int[] f;
    private int max = Integer.MAX_VALUE;
    private int time;

    enum Color {
        WHITE, GRAY, BLACK
    }

    public int getNodeCount() {
        return nodeCount;
    }

    public int getEdgeCount() {
        return edgeCount;
    }

    public int getConsumerConut() {
        return consumerConut;
    }

    public Node[] getFirstArray() {
        return firstArray;
    }

    public Map<Integer, Integer>[] getConsumerArray() {
        return consumerArray;
    }

    //通过广度遍历得到 代价小于deep的节点
    public Set<Integer> BFS(int s, int deep) {
        Queue<Integer> q = new LinkedList<>();
        Set<Integer> set = new HashSet<>();
        int u = 0;

        if (color[s] == Color.BLACK)
            System.out.println("该节点已经遍历过了！");
        else {
            color[s] = Color.GRAY;
            set.add(s);
        }

        d[s] = 0;
        q.offer(s);
        int i = 0;
        while (q.size() != 0) {
            u = q.poll();
            HashMap<Integer, Integer> bw = firstArray[u].bandwidth;
            HashMap<Integer, Integer> cs = firstArray[u].cost;
            Set<Integer> adju = bw.keySet();
            for (Integer v : adju) {
                if (color[v] == Color.WHITE && d[u] < deep) {
                    d[v] = d[u] + bw.get(v) * cs.get(v);
                    if (d[v] > deep) break;
                    color[v] = Color.GRAY;
                    pai[v] = u;
                    q.offer(v);
                    set.add(v);
                }
            }
            color[u] = Color.BLACK;
            i++;
            System.out.println("第" + i + "个" + u + " 花费" + d[u]);

        }
        return set;
    }

    public void print_Path(int s, int v) {
        if (v == s)
            System.out.println(s);
        else if (pai[v] == -1)
            System.out.println("s-->v no path");
        else {
            print_Path(s, pai[v]);
            System.out.println(v);
        }

    }

    void initialize_Single_Source(int s) {
        //foreach vertex v in V[G]
        //do d[v]=INFINITE;
        // pai[v]=NIL;
        //d[s]=0;
        for (int v = 0; v < nodeCount; v++) {
            d[v] = Integer.MAX_VALUE;
            pai[v] = -1;
        }
        d[s] = 0;

    }

    //松弛算法
    void relax(int u, int v, int cvu, Queue<Integer> pq) {
        if (d[v] > d[u] + cvu) {


            pq.remove(d[v]);

            d[v] = d[u] + cvu;

            pq.add(d[v]);
            color[v] = Color.GRAY;
            pai[v] = u;
        }

    }


    public Set<Integer> dijiKstra(int s, int deep) {
        initialize_Single_Source(s);
        Set<Integer> set = new HashSet<>();

        //放节点v 排序关键字为 d[v]
        Queue<Integer> pq = new PriorityQueue<Integer>(nodeCount);
        int i = 0;

        for (int v = 0; v < nodeCount; v++) {
            pq.offer(d[v]);
        }

        while (!pq.isEmpty()) {
            int u = pq.poll();
            set.add(u);
            HashMap<Integer, Integer> bw = firstArray[u].bandwidth;
            HashMap<Integer, Integer> cs = firstArray[u].cost;
            Set<Integer> adju = bw.keySet();
            for (Integer v : adju) {
                int cvu = bw.get(v) * cs.get(v);
                relax(u, v, cvu, pq);

                //d[v]变化了，更新pq
            }
            color[u] = Color.BLACK;
            i++;
            System.out.println("第" + i + "个" + u + " 花费" + d[u]);
        }
        return set;
    }


    //DFS + 拓扑排序 对每一个节点v f[v] finished后插入链表
    public void DFS_VISIT(int u, List sorted) {
        // color[u]=gray
        // time=time+1
        // d[u]=time
        // foreach v in adju[u]
        //      do if color[v]=white
        //         then pai[v]=u
        //              DFS-VISIT(v)
        // color[u]=black
        // time=time+1;
        // f[u]=time;
        color[u] = Color.GRAY;
        time++;
        d[u] = time;
        HashMap<Integer, Integer> bw = firstArray[u].bandwidth;
        HashMap<Integer, Integer> cs = firstArray[u].cost;
        Set<Integer> adju = bw.keySet();
        for (Integer v : adju) {
            if (color[v] == Color.WHITE) {
                pai[v] = u;
                DFS_VISIT(v, sorted);
            }
        }
        color[u] = Color.BLACK;
        time++;
        f[u] = time;
        sorted.add(u);

    }

    public void DFS_VISIT(int u) {
        // color[u]=gray
        // time=time+1
        // d[u]=time
        // foreach v in adju[u]
        //      do if color[v]=white
        //         then pai[v]=u
        //              DFS-VISIT(v)
        // color[u]=black
        // time=time+1;
        // f[u]=time;
        color[u] = Color.GRAY;
        time++;
        d[u] = time;
        HashMap<Integer, Integer> bw = firstArray[u].bandwidth;
        HashMap<Integer, Integer> cs = firstArray[u].cost;
        Set<Integer> adju = bw.keySet();
        for (Integer v : adju) {
            if (color[v] == Color.WHITE) {
                pai[v] = u;
                DFS_VISIT(v);
            }
        }
        color[u] = Color.BLACK;
        time++;
        f[u] = time;
    }

    public void DFS() {
        //foreach vertex u in V[G]
        //      do color[u]=white
        //          pai[u]=NIL
        //time=0
        //foreach vertex u in V[G]
        //      do if color[u]=white
        //          then DFS-VISIT(u)
        time = 0;
        for (int v = 0; v < nodeCount; v++) {
            if (color[v] == Color.WHITE)
                DFS_VISIT(v);
        }

    }


    //拓扑排序
    public List TOPOLOGICAL_SORT() {
        //foreach vertex u in V[G]
        //      do color[u]=white
        //          pai[u]=NIL
        //time=0
        //foreach vertex u in V[G]
        //      do if color[u]=white
        //          then DFS-VISIT(u)
        List sorted = new ArrayList();
        time = 0;
        for (int v = 0; v < nodeCount; v++) {
            if (color[v] == Color.WHITE)
                DFS_VISIT(v, sorted);
        }
        return sorted;
    }


    //http://blog.csdn.net/coder_oyang/article/details/48195405
    //最小生成树 kruskal 和 prim 都是贪心算法
    // Kruskal适合稀疏图，Prim适合稠密图。但它们从渐进意义上好的实现的复杂度是相等的。
    public int GENERIC_MST(int w) {
        //基本思路
        //A<---(NULL)
        //while A does not form a spanning tree
        //      do find an edge(u,v) that is safe for A
        //      A<---A U {(u,v)}
        //return A
        return w;
    }


    //KRUSKAL
/*
    MST-KRUSKAL(G,w)
    A <- empty
    for each vertex v from V[G]
            do MAKE-SET(v)
    //add safe edge to form tree
    sort the edges of E into nondecreasing order by weight w
    for each edge(u,v) from E
       do if FIND-SET(u) != FIND-SET(v)
    then A <- A + {(u,v)}
    UNION(u,v)
    return A

    */

    //Prim
/*
    MST-PRIM(G,w,r)
    for each u from V[G]
            do key[u] <- inf //infinity
    pre[u] <- NULL
    key[r] <- 0
    Q <- V[G]
            //add safe edge to form tree
            while Q != empty
       do u <- EXTRACT-MIN(Q)
          for each v from Adj[u]
            do if v from Q and w(w,v) < key[v]
    then pre[v] <- u
    key[v] <- w(u,v)

    */
    //floyd最短路径。 动态规划思路

    public static void floyd(String[] args) {
        //1.描述最优解的结构
        // -----最短路径解的结构
        // d(i,j)=d(i,k)+w(k,j)

        //2.递归定义一个最优解的值
        // ------------每对顶点间最短路径问题的一个递归解
        // l(i,j,m)=min(l(i,k,m-1)+w(k,j))


        //3.按自底而上的方式计算一个最优解的值
        // ------自底而上计算最短路径的权值
        // L(1)=W L(2)=W*W .....

    }

    public static void main(String[] args) {


    }


    public Graph(int nodeCount, int edgeCount, int consumerConut) {
        this.nodeCount = nodeCount;
        this.edgeCount = edgeCount;
        this.consumerConut = consumerConut;
        this.firstArray = new Node[nodeCount];
        this.consumerArray = new HashMap[consumerConut];
        this.color = new Color[nodeCount];
        this.d = new int[nodeCount];
        this.pai = new int[nodeCount];

        for (int i = 0; i < nodeCount; i++) {
            this.firstArray[i] = new Node();
            color[i] = Color.WHITE;
            d[i] = Integer.MAX_VALUE;
            pai[i] = -1;
        }

        for (int i = 0; i < consumerConut; i++) {

            this.consumerArray[i] = new HashMap<>();

        }

    }
}
